package com.sourcetrip.algorithm.sort.shell;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2021/1/4
 * @description: 十大排序算法之七：希尔排序排序（的对象比较版本） --
 * 可以看做是 insert sort 的升级版本.
 * 利用增量序列，完成数组中间隔部分有序，目的是为了减少逆序对。
 * 其中细节是通过 insertion sort 完成有序。
 */
public class ShellCustomedSortV0<E> extends AbstractCustomedObjectSort<E> {

	/**
	 * 增量序列
	 */
	static List<Integer> list = new ArrayList<>();
	private E cur = null;
	private int swapIndex = 0;
	private int lastIndex = 0;

	/**
	 * 1.获取增量序列；
	 * 2.根据增量序列完成 insert sort
	 *
	 * @param objectArr
	 */
	@Override
	protected void sortArr(E[] objectArr) {
		getShellList(objectArr);
		for (Integer step :
				list) {
			//第 col 列，至少说明了该列的最小索引
			for (int col = 0; col < step; col++) {
				for (int i = col + step; i < objectArr.length; i += step) {
					swapIndex = i;
					lastIndex = i - step;
					cur = objectArr[i];
					while (lastIndex > -1 && compare(cur, objectArr[lastIndex]) < 0) {
						swap(swapIndex, lastIndex);
						swapIndex = lastIndex;
						lastIndex -= step;
					}
					objectArr[swapIndex] = cur;
				}
			}

		}

	}


	//region	core methods

	/**
	 * 获取希尔数列
	 */
	private void getShellList(E[] objectArr) {
		if (list.size() == 0) {
			//getDefaultShellList(list, objectArr);
			getSedgewickShellList(list, objectArr);
		}
	}

	/**
	 * 获取希尔默认序列
	 * DM=⌊N/2⌋,Dk=⌊Dk+1/2⌋
	 * 最坏情况是当奇数升序，偶数升序，但是偶数大于奇数。
	 * 甚至比 insertion sort 还慢！增量序列不起作用！
	 *
	 * @param list
	 * @param objectArr
	 */
	private void getDefaultShellList(List<Integer> list, E[] objectArr) {
		int size = objectArr.length >> 1;
		while (size >= 1) {
			list.add(size);
			size = size >> 1;
		}

	}

	/**
	 * 获取 Sedgewick 增量序列
	 * 最坏时间复杂度为O(N4/3)；平均时间复杂度约为O(N7/6)
	 * 但是在官方库中默认的还是 归并/快速排序
	 *
	 * @param list
	 * @param objectArr
	 */
	private void getSedgewickShellList(List<Integer> list, E[] objectArr) {
		int k = 0, step = 0;
		while (true) {
			if (k % 2 == 0) {
				int pow = (int) Math.pow(2, k >> 1);
				step = 1 + 9 * (pow * pow - pow);
			} else {
				int pow1 = (int) Math.pow(2, (k - 1) >> 1);
				int pow2 = (int) Math.pow(2, (k + 1) >> 1);
				step = 1 + 8 * pow1 * pow2 - 6 * pow2;
			}
			if (step >= objectArr.length) {
				break;
			}
			list.add(0, step);
			k++;
		}
	}


	//endregion


}
